Mobile unmanned vehicles (also referred to as autonomous mobile robots or self-driving vehicles) operate in a wide variety of environments. Such environments can have various physical characteristics that the vehicles may be required to navigate around, interact with and the like, in order to operate successfully. Physical characteristics such as those mentioned above can generally be represented in maps of the environments stored by the vehicles. The operating environments of the vehicles, however, may also impose other restrictions on the operation of the vehicles that do not arise directly from physical characteristics of the environments, or that arise from physical characteristics that are not readily detectable by the vehicles. Such restrictions are less suitable for representation in maps, and can therefore render the operation of self-driving vehicles difficult.